1. Field of the Invention
The present invention relates to data compression and, more particularly, to a method and system for compressing the repeat request data in Automatic Repeat reQuest (ARQ) protocols used in telecommunication systems.
2. Description of the Related Art
In many telecommunication systems such as the Universal Mobile Telecommunication System (UMTS), data is transmitted over a communication channel in blocks of predefined sizes. During the transmission, the blocks may become corrupted in spite of various preventive measures and error correction techniques used, such as forward-feed error correction (FEC). Through the use of cyclic redundancy checks (CRC), the corrupted or erroneous blocks can be detected with a high degree of accuracy and reliability. Once the errors are detected, a request for retransmission of the corrupted or erroneous blocks, called a repeat request, may be issued. Issuance of the repeat request is usually done as part of an Automatic Repeat reQuest (ARQ) protocol, which is a common procedure used in modern telecommunication systems, such as UTMS, to recover from erroneous block transmissions.
FIG. 1 is a functional block diagram illustrating an exemplary portion of a typical telecommunication system. As can be seen, the system includes a sender unit 102 that is configured to send blocks of data to a receiver unit 104 over a communication channel 106. Whenever possible, the sender unit 102 tries to transmit a continuous stream of blocks to the receiver unit 104. At the receiver unit 104, the data blocks are verified (e.g., using a CRC) to ensure the data is correctly received. If one or more blocks of data are found to be corrupted or otherwise erroneous, the receiver unit 104 issues a request to the sender unit 102 to retransmit the bad blocks. The repeat request typically includes a series or sequence of bits composed in such a way so as to represent or otherwise indicate which particular blocks need to be retransmitted. Such a request sequence is designated as Rs in FIG. 1. The timing of the request sequence Rs is usually at regular intervals that may vary in accordance with the system""s ARQ protocol.
A number of techniques exist for composing the request sequence Rs. One such technique, called a xe2x80x9clistxe2x80x9d technique, involves listing the sequence number of the blocks that need to be retransmitted. During normal transmission, each block is assigned one number in a sequence of numbers of a predetermined length. At the receiver end, the sequence number of the block that is corrupted or erroneous is determined, then sent as part of the request sequence Rs to identify the blocks that need to be retransmitted.
Another technique, called a xe2x80x9cbitmapxe2x80x9d technique, involves using a string of 1s and 0s in the request sequence Rs to identify the blocks that need to be retransmitted. In this technique, a 1 or a 0 is used to denote each block that was received. For example, a 1 may be used to denote a block that has been successfully received and a 0 to denote a block that is erroneous or idle (i.e., no block was received). Thus, a type of bitmap representing the received blocks may be composed with the 0s indicating the blocks that need to be retransmitted.
For very long sequences, however, neither of the above techniques are very practical or economical in terms of bandwidth usage. Therefore, in general, some encoding (compression) of the data in the request sequence Rs is needed.
Data compression can be efficiently performed when certain statistical parameters about the data that is to be compressed are known (e.g., type of data, length of data, generating source). The difficulty with encoding the data in the request sequence Rs, however, is that very little statistical information about the data can be used. For example, although there is a significant amount of correlation between consecutive request sequences, it is uncertain whether one or more of the transmitted sequences will actually be received by the sender unit. Hence, it is usually assumed that there is no correlation between the request sequences Rs (i.e., a decision is made not to use any correlation data). Thus, the probability of any particular combination or distribution of erroneous blocks occurring for a given sequence of transmitted blocks is usually unknown. Due to this lack of knowledge, most presently available algorithms used to compress the ARQ request sequence are xe2x80x9cuniversal,xe2x80x9d that is to say, they can adapt their compression scheme to the unknown parameters of a known statistical model of the data or a set of models.
Consider the bitmap approach described above. If no errors occur during the transmission, then the request sequence Rs becomes a binary sequence 111 . . . 100 . . . 0 of a given length N. Any such sequence may be described entirely by its length of n* number of 1s, which is less than or equal to N (that is, n*xe2x89xa6N), and it is sufficient to encode (describe) n* by either a uniform coding (e.g., of length (log2 N)) or a variable length prefix coding. The advantages of such variable length coding are not clearly obvious and, therefore, if one assumes a uniform coding is used, the result is a compression with a ratio of N/(log2 N).
If block errors occur, the errors result in the substitution of the continuous run of 1s in the request sequence Rs 11 . . . 100 . . . 0 by a binary sequence xn that includes both 1s and 0s mixed together, where nxe2x89xa7n*, but the value of N does not change (that is to say, the length of the run of trailing 0s decreases). The problem, therefore, is to be able to describe the value of n and xn using as efficient a coding as possible. The most efficient coding of xn, which is a bitmap of the errors, is based on knowing the probability of any/all bitmaps of a given length n occurring. Unfortunately, the probabilities of these bitmaps occurring are usually not known. Sometimes, a known source model (e.g., a two state Markov model), or a rather narrow set of such models, is used for increasing the coding efficiency. This is referred to as xe2x80x9cuniversalxe2x80x9d coding. For compression of the request sequence data, however, such universal coding does not work well because the statistical properties of the bitmaps are defined by the statistical properties of the error sequence eq=e1, . . . , en, where eixcex5{0, 1} and by the ARQ algorithm, and both of these xe2x80x9ccomponentsxe2x80x9d are practically unknown and/or very complex to describe.
In fact, error sequences are xe2x80x9cgeneratedxe2x80x9d by many sources of many different natures, and their mixture in different proportions defines a very wide class of possible sources. However, even for a small set of source models (or just one model), one cannot translate the statistics of the error sequence into the statistics of the bitmaps. For one thing, the complexity of any ARQ algorithm leaves little chances of solving this problem. Thus, the problem of compressing the request sequence data can be generalized as one of encoding (compressing) the output of a xe2x80x9cblack boxxe2x80x9d (i.e., the ARQ algorithm) using input signals (i.e., the error sequence) that are unknown (from the sender""s perspective).
Accordingly, it is desirable to be able to provide a method and system for compressing the data in the request sequence of an ARQ algorithm, and to be able to do so in a way that is both computationally efficient and simple to implement.
The present invention is related to a method and system for compressing the data in the request sequence of an ARQ algorithm. The system and method of the present invention include an entropy encoder module and a probability estimation module. The probability estimation module receives the request sequence from the ARQ algorithm and estimates a probability associated with each symbol or bit in the sequence according to a customized Markov model. The estimated probabilities are thereafter provided to the entropy encoder module, which uses the estimated probabilities to encode each symbol or bit in the request sequence. The encoded request sequence is then transmitted in a repeat request in accordance with the ARQ algorithm.
In general, in one aspect, the invention is related to a method of encoding a request sequence from an automatic repeat request system. The method comprises the steps of receiving the request sequence from the automatic repeat request system, each request sequence including a sequence of binary symbols, and counting a number of 0s and 1s in the sequence of binary symbols in accordance with a Markov model. The method further comprises estimating a probability associated with each binary symbol based on the number of 0s and 1s counted in each state of the Markov model, and encoding the binary symbols on a symbol-by-symbol basis using the probability estimates.
In general, in another aspect, the invention is related to a method of decoding an encoded request sequence from an automatic repeat request system. The method comprises the steps of receiving the encoded request sequence from the automatic repeat request system, and decoding the encoded request sequence into a sequence of binary symbols on a symbol-by-symbol basis. The method further comprises counting a number of 0s and 1s in the sequence of binary symbols in accordance with a Markov model, and estimating a probability associated with each binary symbol based on the number of 0s and 1s counted in each state of the Markov model.
In general, in still another aspect, the invention is related to an encoder for encoding a request sequence from an automatic repeat request system. The encoder comprises a probability estimation module configured to receive the request sequence including a sequence of binary symbols from the automatic repeat request system, the probability estimation module further configured to count a number of 0s and 1s in the sequence of binary symbols in accordance with a Markov model, and to estimate a probability associated with each binary symbol based on the number of 0s and 1s counted in each state of the Markov model. The encoder further comprises an encoder module configured to encode the binary symbols on a symbol-by-symbol basis using the probability estimates thereof.
In general, in yet another aspect, the invention is related to a decoder for decoding an encoded request sequence from an automatic repeat request system. The decoder comprises a decoder module configured to receive the encoded request sequence and to decode the encoded request sequence into a sequence of binary symbols, wherein the decoder module decodes the encoded request sequence on a symbol-by-symbol basis. The decoder further comprises a probability estimation module configured to count a number of 0s and 1s in the sequence of binary symbols in accordance with a Markov model, and to estimate a probability associated with each binary symbol based on the number of 0s and 1s counted in each state of the Markov model.
It should be emphasized that the term comprises/comprising, when used in this specification, is taken to specify the presence of stated features, integers, steps, or components, but does not preclude the presence or addition of one or more other features, integers, steps, components, or groups thereof.